package heap;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-05-29
 * Time: 23:53
 */
public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[10];
    }
    //建堆
    public void creativeHeap(int[] array){
        //准备数组元素，这一步可以省略
        for(int i=0;i<array.length;++i){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //每个孩子都需要向下调整
        //从最后一个根节点开始向下调整
        for(int root = (this.usedSize-1-1)/2;root>=0;root--){
            shiftDown(root,this.usedSize);
        }

    }
    //交换两个元素的值
    public void swap(int[] elem,int i,int j){
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }

    public void shiftDown(int root,int len){
        int parents = root;
        int child = 2*parents+1;
        while(child<len){
            //选出左右孩子中最大的，并且这里要注意child+1不能越界
            if(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            //此时child是左右孩子中最大的
            //看是否需要与parent进行交换
            if(this.elem[child]>this.elem[parents]){
                //如果发现左右孩子中节点的最大的值大于父节点，那就需要进行交换
                swap(this.elem,parents,child);
                //交换完之后parents和child需要改变
                parents = child;
                child= 2*parents+1;
            }else{
                //如果父节点大于左右孩子节点的值那就跳出循环
                break;
            }
        }
    }

    public boolean isFull(){
        return this.usedSize==this.elem.length;
    }


    public void shiftUp(int child){
       //进行向上调整
        int parents = (child-1)/2;
        while(child>0){
            if(this.elem[parents]<this.elem[child]){
                swap(this.elem,parents,child);
                child=parents;
                parents = (child-1)/2;
            }else {
                break;
            }
        }
    }

    //堆的插入
    public void offer(int val){
        //如果满了需要增容
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //将值插入到最后一个位置
        this.elem[usedSize] = val;
        this.usedSize++;
        shiftUp(this.usedSize-1);
    }

    public boolean isEmpty(){
        return this.usedSize==0;
    }

    //堆的删除
    public void poll(){
        if(isEmpty()){
            System.out.println("堆已经满了！！！");
            return;
        }
        //将堆顶元素与最后一个元素交换，然后从堆顶元素开始进行向下调整
        swap(this.elem,0,this.usedSize-1);
        this.usedSize--;
        shiftDown(0,this.usedSize);

    }

    //堆排序



    //topK问题




}
